#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000000

typedef struct node4{
	int data;
	int weight;
	struct node4* next;
}Adj;

typedef struct node5{
	int degree;
	Adj* next;
}Graph;


int numberOfEdges(const char name[])
{
	FILE* fp1 = fopen(name, "rb");
	if(fp1 == NULL){
	    printf("open error\n");
	    exit(1);
	}
	int edges = 0;
	int u, v, weight;
	while(!feof(fp1)) {
	    fscanf(fp1,"%d%d%d", &u, &v, &weight);
            edges++;	
	}
	fclose(fp1);
	return edges;
}

int numberOfVertices(const char name[])
{
	FILE*fp1 = fopen(name, "rb");
	if(fp1 == NULL){
	    printf("open error\n");
	    exit(1);
	}
	char *point = (char*)malloc(MAXSIZE*sizeof(char));
	int i;
	for(i = 0; i < MAXSIZE; i++){
	    point[i] = 0;
	}
	int vertices = 0;
	int u, v, weight;
	while(!feof(fp1)){
	    fscanf(fp1,"%d%d%d", &u, &v, &weight);
	    point[u] = point[v] = 1;
	}
	for(i = 0;i < MAXSIZE; i++){
	    if(point[i] == 1 )
	        vertices++;
	}
        fclose(fp1);
	return vertices;
}

double freemanNetworkCentrality(const char name[])
{
        FILE* fp1 = fopen(name,"rb");
	if(fp1 == NULL){
	    printf("open error\n");
	    exit(1);
	}
	 
	Adj *newnode, *q;

	Graph *G = (Graph*)malloc(MAXSIZE*sizeof(Graph));
	int i;
	for(i = 0; i < MAXSIZE; i++){
	    G[i].next = NULL;
	    G[i].degree = 0;
	}
	
	int u1, v1, weight1;
	while(!feof(fp1)){
	    fscanf(fp1,"%d%d%d", &u1, &v1, &weight1);
            q = G[u1].next;
            while(q != NULL){
        	if(q->data == v1){
        	    break;
		}
		q = q->next;
	    }
	    if(q == NULL){
	        newnode = (Adj*)malloc(sizeof(Adj));
	        newnode->data = v1;
	        newnode->next =G[u1].next;
	        G[u1].next = newnode;
	        G[u1].degree++;
	        newnode = (Adj*)malloc(sizeof(Adj));
	        newnode->data = u1;
	        newnode->next = G[v1].next;
	        G[v1].next = newnode;
	        G[v1].degree++;
	    }
	}
	int maxdegree = 0; 
	int sumdegree = 0;
	
	for(i = 0; i < MAXSIZE; i++){
	    if(G[i].degree > maxdegree){
		maxdegree = G[i].degree;
	    }
	    sumdegree += G[i].degree;
	}

	int vertice = numberOfVertices(name);
	double centrality;
	centrality = (double)(vertice*maxdegree - sumdegree) / (vertice - 1) / 
        (vertice - 2);
	return  centrality; 
}
